// https://www.lintcode.com/problem/01-matrix/my-submissions

class Solution {
public:
    /**
     * @param matrix: a 0-1 matrix
     * @return: return a matrix
     */
    
    
    // 法一：BFS
    // struct Node
    // {
    //     int x;
    //     int y;
    // };
    // vector<vector<int>> updateMatrix(vector<vector<int>> &matrix) {
    //     int dx[4] = {-1, 0, 1, 0};
    //     int dy[4] = {0, 1, 0, -1};
    //     queue<Node> q;
    //     int m = matrix.size();
    //     int n = matrix[0].size();
    //     vector<vector<int>> dis(m, vector<int>(n, -1));
    //     for (int i = 0; i < m; ++i)
    //     {
    //         for (int j = 0; j < n; ++j)
    //         {
    //             if (matrix[i][j] == 0)
    //             {
    //                 q.push(Node{i, j});
    //                 dis[i][j] = 0;
    //             }
    //         }
    //     }
    //     while (!q.empty())
    //     {
    //         Node tmp = q.front();
    //         q.pop();
    //         for (int i = 0; i < 4; ++i)
    //         {
    //             int newX = tmp.x + dx[i];
    //             int newY = tmp.y + dy[i];
    //             if (newX < 0 || newX >= m || newY < 0 || newY >= n || dis[newX][newY] != -1)
    //                 continue;
    //             int val = dis[tmp.x][tmp.y] + 1;
    //             dis[newX][newY] = val;
    //             q.push(Node{newX, newY});
    //         }
    //     }
    //     return dis;
    // }
    
    
    // vector<vector<int>> updateMatrix(vector<vector<int>> &matrix) {
    //     int move[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    //     queue<pair<int, int>> q;
    //     int m = matrix.size();
    //     int n = matrix[0].size();
    //     vector<vector<int>> dis(m, vector<int>(n, -1));
    //     for (int i = 0; i < m; ++i)
    //     {
    //         for (int j = 0; j < n; ++j)
    //         {
    //             if (matrix[i][j] == 0)
    //             {
    //                 q.push(make_pair(i, j));
    //                 dis[i][j] = 0;
    //             }
    //         }
    //     }
    //     while (!q.empty())
    //     {
    //         pair<int, int> tmp = q.front();
    //         q.pop();
    //         for (int i = 0; i < 4; ++i)
    //         {
    //             int newX = tmp.first + move[i][0];
    //             int newY = tmp.second + move[i][1];
    //             if (newX < 0 || newX >= m || newY < 0 || newY >= n || dis[newX][newY] != -1)
    //                 continue;
    //             int val = dis[tmp.first][tmp.second] + 1;
    //             dis[newX][newY] = val;
    //             q.push(make_pair(newX, newY));
    //         }
    //     }
    //     return dis;
    // }
    
    // 法二：动态规划
    // 从左上出发推一遍。
    // 从右下出发推一遍。
    vector<vector<int>> updateMatrix(vector<vector<int>> &matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dis(m, vector<int>(n, INT_MAX));
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (matrix[i][j] == 0) dis[i][j] = 0;
                else
                {
                    if (i > 0 && dis[i - 1][j] != INT_MAX) //注意用INT_MAX初始化要判断
                        dis[i][j] = min(dis[i][j], dis[i - 1][j] + 1);
                    if (j > 0 && dis[i][j - 1] != INT_MAX)
                        dis[i][j] = min(dis[i][j], dis[i][j - 1] + 1);
                }
            }
        } 
        
        for (int i = m - 1; i >= 0; --i)
        {
            for (int j = n - 1; j >= 0; --j)
            {
                if (i < m - 1 && dis[i + 1][j] != INT_MAX)
                    dis[i][j] = min(dis[i][j], dis[i + 1][j] + 1);
                if (j < n - 1 && dis[i][j + 1] != INT_MAX)
                    dis[i][j] = min(dis[i][j], dis[i][j + 1] + 1);
            }
        }
        return dis;
    }
};